1. Field of the Invention
The invention relates to a method of detecting and possibly correcting errors caused by loss of synchronization of a data sink with a data source in a data transmission system using a linear block code.
2. Description of the Related Art
In a data transmission system having a data sink and a data source messages are exchanged between the sink and the sources over transmission channels. Such messages may have a word structure and consist, for example, of linked code words in a linear block code. A block code is a code in which all code words are of equal lengths, a sequence of symbols (or source words) to be encoded being divided into blocks of equal lengths. A systematic code is one in which a particular code word is assigned to each of the symbols or source words provided by the data source. In a linear systematic block code each linear combination of code words also constitutes a code word.
Consecutive code words are linked and transmitted in a continuous sequence over the transmission channel. In order to be separated at the receiver, it is necessary to synchronize the decoder therein with the encoding effected at the transmitter. This is denoted word synchronization.
In "Fehlerkorrigierende Block-Codierung fur die Datenubertragung" by F. J. Furrer, Birkhauser Verlag, 1981, pages 238 to 250, a description is given of methods of word synchronization for consecutively transmitted code words using synchronization samples, codes with binary prefixes, separable codes and synchronizable codes. Which synchronization method is chosen, as well as the method of encoding, depends on the properties of the transmission channel. For the purpose of synchronization, a synchronization sample can be used which is a fixed bit sequence of a predetermined length and which is known to the receiver (see, for example, ISO recommendation 3309-1979). However, including a synchronization sample at the beginning of a message and repeating it at predetermined distances (numbers of bits) within the message reduces the effective data transmission speed of the transmission channel.
A further method of word synchronization is disclosed in "Error-Correcting Codes" by Peterson/Weldon, 2nd Edition 1972 at pages 374 to 390. In this method all the sequentially transmitted code words are linked to the same error protection word, whereby a bit-wise shift of the code words of a message can be recognized. The protection word, which is not a code word, is added at the transmitter and subtracted at the receiver. On page 379 an example is described in which the protection word for a binary code is chosen to be equal to "1", as a result of which the last bit of each of the code words is inverted. If the code words are shifted through one or more bit positions, then, because of the fact that the encoding instruction is violated, this bit shift can be recognized and possibly corrected at the receiver.
So as to render it possible to use codes which recognize or correct randomly occurring errors, which may occur in transmission over channels which are susceptible to interference and have error bursts, for example radio transmission channels, the individual code words can be interleaved bit-wise prior to transmission. For the purpose of bit-sequential interleaving the first bit of each of the code words is transmitted, then the second bit of each of the code words, and so on until the last bits of all the coce words of the messages are joined together. Such interleaving is described in the article by B. Dorsch "Performance and Limits of Coding for Simple Time Varying Channels", 1980, International Zurich Seminar on Digital Communications, Proceedings IEEE Catalog No. 80 CH 1521-4, left-hand column of page G 1.1).